package com.base.dataStructure.Tree;

/**
 * @Author: hdhao
 * @Create: 2023/4/6 - 20:05
 * @Version: v1.0
 */
//二叉搜索树
public class BSTTree2<T extends Comparable<T>,V> {
    //根节点
    BSTNode<T,V> root;

    public V get(T key) {
        if (key == null) {
            return null;
        }
        BSTNode<T,V> node = root;
        while (node != null) {
            /*
                -1: key < node.key
                0:key = node.key
                1:key > node.key
             */
            int res = key.compareTo(node.key);
            if (res < 0) {
                node = node.left;
            } else if (res > 0) {
                node = node.right;
            } else {
                return node.value;
            }
        }
        return null;
    }

    static class BSTNode<T,V>{
        T key;
        V value;
        BSTNode<T,V> left;
        BSTNode<T,V> right;

        public BSTNode(T key) {
            this.key = key;
        }

        public BSTNode(T key, V value) {
            this.key = key;
            this.value = value;
        }

        public BSTNode(T key, V value, BSTNode<T,V> left, BSTNode<T,V> right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }
}
